﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.SequenceComparison.LCS
{
    public class LongestCommonSubsequence<T>
    {
        private readonly EqualityComparison<T> _equalityComparison;

        public LongestCommonSubsequence(EqualityComparison<T> equalityComparison = null)
        {
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
        }

        public int Length(IList<T> x, IList<T> y)
        {
            var LCS = new int[x.Count + 1][];
            for (int i = 0; i <= x.Count; i++)
            {
                LCS[i] = new int[y.Count + 1];
            }
            for(int j = 1; j <= y.Count; j++)
            {
                LCS[0][j] = 0;
                for(int i = 1; i <= x.Count; i++)
                {
                    if ( _equalityComparison(x[i-1],y[j-1]) )
                    {
                        LCS[i][j] = LCS[i - 1][j - 1] + 1;
                    }
                    else
                    {
                        LCS[i][j] = Math.Max(LCS[i - 1][j], LCS[i][j - 1]);
                    }
                }
            }

            return LCS[x.Count][y.Count];
        }

        public IList<T> Subsequence(IList<T> x, IList<T> y)
        {
            var LCS = new int[x.Count + 1][];
            for (int i = 0; i <= x.Count; i++)
            {
                LCS[i] = new int[y.Count + 1];
            }
            var back = new Tuple<int,int>[x.Count + 1][];
            for(int i = 0; i <= x.Count; i++)
            {
                back[i] = new Tuple<int,int>[y.Count+1];
                back[i][0] = new Tuple<int, int>(i,0);
            }

            for(int j = 1; j <= y.Count; j++)
            {
                LCS[0][j] = 0;
                back[0][j] = new Tuple<int, int>(0,j);
                for(int i = 1; i <= x.Count; i++)
                {
                    if ( _equalityComparison(x[i-1],y[j-1]) )
                    {
                        LCS[i][j] = LCS[i - 1][j - 1] + 1;
                        back[i][j] = new Tuple<int, int>(i-1,j-1);
                    }
                    else if ( LCS[i-1][j] > LCS[i][j-1])
                    {
                            LCS[i][j] = LCS[i - 1][j];
                            back[i][j] = new Tuple<int, int>(i - 1, j);
                    }
                    else
                    {
                            LCS[i][j] = LCS[i][j - 1];
                            back[i][j] = new Tuple<int, int>(i, j - 1);
                    }
                }
            }
            int r = x.Count;
            int q = y.Count;
            var sequence = AlgoritmiaFactory.Lists<T>.Default;
            while ( back[r][q].Item1 != r || back[r][q].Item2 != q)
            {
                var tp = back[r][q];
                if ( tp.Item1 == r-1 && tp.Item2 == q-1 )
                {
                    sequence.Add(x[r-1]);
                }
                r = tp.Item1;
                q = tp.Item2;
            }
            return sequence.Reverse().ToAlgoritmiaList();
        }
    }

     public class LongestCommonSubsequence : LongestCommonSubsequence<char>
     {
         public int Length(string x, string y)
         {
             return base.Length(x.ToAlgoritmiaList(), y.ToAlgoritmiaList());
         }

         public string Subsequence(string x, string y)
         {
             return new string(base.Subsequence(x.ToAlgoritmiaList(), y.ToAlgoritmiaList()).ToArray());
         }

     }
}
